public class Test8_1 {
    private static class BinartyTree{
        private int val;
        private BinartyTree left;
        private BinartyTree right;
        private BinartyTree parent;

        public BinartyTree() {
        }

        public BinartyTree(int val) {
            this.val = val;
        }
        @Override
        public String toString(){
            return val+" ";
        }
    }
    public static BinartyTree getNext(BinartyTree node){
        if (node == null) return  null;
        //保存下一个节点
        BinartyTree target = null;
        //如果节点的右节点不为空
        if (node.right != null){
            target = node.right;//此节点的右节点为下一个节点
            while (target.left != null){//如果当前节点还有左字节点
                target = target.left;//找到最末尾的左子节点
            }
            return  target; //返回下一个节点
        }else if (node.parent != null){//如果当前节点的父节点不为空
            target = node.parent;
            BinartyTree cur = node;
            // 如果父结点不为空，并且，子结点不是父结点的左子节点
            while(target != null && target.left != cur){
                cur = target;//一直找到左子节点不为node的父节点，为下一个节点
                target = target.parent;
            }
            //如果当前节点是父节点的左节点，直接输出父节点
            return target;
        }
        return null;
    }
    private static void assemble(BinartyTree node,
                                 BinartyTree left,
                                 BinartyTree right,
                                 BinartyTree parent) {
        node.left = left;
        node.right = right;
        node.parent = parent;
    }

    public static void main(String[] args) {
        /*
                            1
                  2                   3
           4         5          6          7
        8     9   10   11   12   13    14   15
         */
        //8 4 9 2 10 5 11 1 12 6 13 3 14 7 15
         BinartyTree n1 = new BinartyTree (1); // 12
         BinartyTree n2 = new BinartyTree (2); // 10
         BinartyTree n3 = new BinartyTree (3); // 14
         BinartyTree n4 = new BinartyTree (4); // 9
         BinartyTree n5 = new BinartyTree (5); // 11
         BinartyTree n6 = new BinartyTree (6); // 13
         BinartyTree n7 = new BinartyTree (7); // 15
         BinartyTree n8 = new BinartyTree (8); // 4
         BinartyTree n9 = new BinartyTree (9); // 2
         BinartyTree n10 = new BinartyTree (10); // 5
         BinartyTree n11 = new BinartyTree (11); // 1
         BinartyTree n12 = new BinartyTree (12); // 6
         BinartyTree n13 = new BinartyTree (13); // 3
         BinartyTree n14 = new BinartyTree (14); // 7
         BinartyTree n15 = new BinartyTree (15); // null

        assemble(n1, n2, n3, null);
        assemble(n2, n4, n5, n1);
        assemble(n3, n6, n7, n1);
        assemble(n4, n8, n9, n2);
        assemble(n5, n10, n11, n2);
        assemble(n6, n12, n13, n3);
        assemble(n7, n14, n15, n3);
        assemble(n8, null, null, n4);
        assemble(n9, null, null, n4);
        assemble(n10, null, null, n5);
        assemble(n11, null, null, n5);
        assemble(n12, null, null, n6);
        assemble(n13, null, null, n6);
        assemble(n14, null, null, n7);
        assemble(n15, null, null, n7);

        System.out.println(getNext(n1));
        System.out.println(getNext(n2));
        System.out.println(getNext(n3));
        System.out.println(getNext(n4));
        System.out.println(getNext(n5));
        System.out.println(getNext(n6));
        System.out.println(getNext(n7));
        System.out.println(getNext(n8));
        System.out.println(getNext(n9));
        System.out.println(getNext(n10));
        System.out.println(getNext(n11));
        System.out.println(getNext(n12));
        System.out.println(getNext(n13));
        System.out.println(getNext(n14));
        System.out.println(getNext(n15));
    }

}

